package leetcode.hot100;
import datastruct.tree.TreeNode;

public class Solution337 {
    //打家劫舍III
    /*动态规划：dp1[root]代表偷了root可以在以root为根的树获得最大收益，dp0[root]代表不偷root可以在root为根的树获得的最大收益
    dp1[root]=max{root.val+dp0[root.left]+dp0[root.right]}
    dp0[root]=max{dp0[root.left]+dp0[root.right],dp1[root.left]+dp0[root.right],
                  dp0[root.left]+dp1[root.right],dp1[root.left]+dp1[root.right]}
    */
    public int rob(TreeNode root) {
        int[] choice = robOrPass(root);
        return Math.max(choice[0],choice[1]);
    }
    public int[] robOrPass(TreeNode root){
        //返回值代表[不偷root可获得最大收益,偷root可获得最大收益]
        if(root==null) return new int[]{0,0};
        //获取从孩子那可获取的最大收益
        int[] leftSupplyMax = robOrPass(root.left);
        int[] rightSupplyMax = robOrPass(root.right);
        //计算不偷root可获得最大收益dp0[root]
        int dp0 = Math.max(leftSupplyMax[0],leftSupplyMax[1])+
                Math.max(rightSupplyMax[0],rightSupplyMax[1]);
        //计算偷root可获得最大收益dp0[root]
        int dp1 = root.val+leftSupplyMax[0]+rightSupplyMax[0];
        return new int[]{dp0,dp1};
    }
}
